package codeTopPractice.dynamicProgram;

import java.util.Map;

/**
 * 本人整理经典动态规划题
 * 题目来自原文：https://blog.csdn.net/hollis_chuang/article/details/103045322?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166385232516782388024743%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166385232516782388024743&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-103045322-null-null.142^v50^control,201^v3^add_ask&utm_term=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&spm=1018.2226.3001.4187
 * 原作者：Hollis Chuang
 */

public class DP {

    public static void main(String[] args) {

        //System.out.println(oneDimensionDP(5));
        //System.out.println(twoDimensionDP(7,3));

        int[][] arr = new int[3][3];
        arr[0][0]=1;
        arr[0][1]=3;
        arr[0][2]=1;
        arr[1][0]=1;
        arr[1][1]=5;
        arr[1][2]=1;
        arr[2][0]=4;
        arr[2][1]=2;
        arr[2][2]=1;

        System.out.println(theShortestPath(arr));
    }


    //一维动态规划
    //假设一个青蛙一次可以跳上1个或2个台阶，求青蛙跳上第n个台阶有几种跳法
    public static int oneDimensionDP(int n){

        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;

        for (int i = 3; i <dp.length; i++) {

            dp[i]=dp[i-1]+dp[i-2];

        }

        return dp[n];
    }

    //二维DP
    //一个机器人位于m*n网格的左上角，每次机器人只能向右或者向下走一格，试求机器人
    //m,n均不超过100
    public static int twoDimensionDP(int m,int n){

        if(m<=0 || n<=0){
            return 0;
        }

        int[][] dp = new int[m][n];
        //初始化值
        for (int i = 0; i < m; i++) {
            dp[i][0]=1;
        }

        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i <m ; i++) {
            for (int j = 1; j <n ; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }

        return dp[m-1][n-1];

    }

    //给出固定矩阵，求从左上方出发，到达右下方的最短路径
    // 如
    // [1,3,1]
    // [1,5,1]
    // [4,2,1]
    // 最短路径为7
    public static int theShortestPath(int[][] arr){

        int m = arr.length;
        int n = arr[0].length;

        if(m<=0 || n<=0){
            return 0;
        }

        //初始化dp
        int[][] dp = new int[m][n];
        dp[0][0]= arr[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + arr[i][0];
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+arr[i][j];
            }
        }
        return dp[m-1][n-1];

    }

}
